(1) Field of the Invention
The present invention relates to the field of image display systems. Specifically, the present invention relates to the field of computer image display systems utilizing geometric graphic primitives.
(2) Prior Art
Computer systems may be implemented with graphics processors for display of computer information and graphic images on a display screen. These displays represent information and data within the computer system that simulate an artificial environment that is generated by the computer image system. One of the primary functions of a graphics processor for image display is to create a visual rendition of a true surface when passed a computerized model for that surface. The surface model or data that represents the visual rendition approximates the true mathematical equations for the true surface. These equations representing the true surface may be generated or given via physics, however, the surface generated by the computer graphic system will be composed of approximations to the true surface. These approximations are accomplished by using simple geometric objects, or graphic primitives, to construct the data model of the true surface. Simple and standardized geometric primitives are utilized by computer display systems because standard, and well understood hardware can be utilized to process these geometric primitives at very high speeds. Moreover many of these hardware processors are specially tailored for a particular type of geometric primitive. Therefore, it is advantageous to break true surfaces down into data models that approximate the true surface but are composed of a multitude of graphic primitives. The manner in which such graphic or geometric primitives are rendered (i.e., displayed on a computer screen), becomes vital to the processing power and efficiency of the overall computer graphic system.
In order to understand aspects and advantages of the present invention over the prior art systems for rendering geometric primitives, a discussion of prior art computer graphic systems is presented herein. Typical graphic or geometric primitives used in computer graphic systems for representing surfaces are the four sided polygon (quadrilateral, with four vertices) and the three sided polygon which is a triangle having three vertices. By constructing a multitude of these graphic primitives and placing them together, a computerized data model can be constructed as an approximation of a true surface. The approximation will be displayed according to processing technology performed in specialized and high speed hardware units.
The Hardware Scan Converter
FIG. 1 illustrates a typical geometric primitive 20 triangle having three vertices 6, 5, and 7. A typical primitive will be defined by a specialized data structure. Graphic processors operate on primitives by operating on specialized data structures of the primitive. The data structure for a primitive is composed of a certain number of vertices with a certain number of parameters or attributes for each vertex. For a triangle primitive, there are three vertices and for a quadrilateral primitive ("quad") there are four vertices. The array notation, TRIANGLE [V][P], represents this triangle primitive 20 of FIG. 1 within the computer graphic system where the size of V represents the number of vertices within the data structure and P represents various parameters that are associated with each vertex of the triangle primitive. A triangle primitive will have V=3 and each of the coordinates that comprise the triangle will be present within the data structure. Further, other parameters that comprise attributes of the triangle are present within the data structure associated with each vertex of each primitive, such as positional information (x, y, z) parameters, color information (read, green, blue, and alpha) parameters, and the surface normal vectors (Nx, Ny, Nz) at each vertex. All of this information is present for each vertex of a graphic primitive. Therefore, for each of the vertices 5, 6, 7 of the triangle 20, the data structure defines position, surface normal vectors, and color. A computer system processing this primitive would have access to all of this information for generation of this primitive accurately onto a computer screen. Similarly, a quadrilateral may be defined by the array notation, QUAD[V][P], where V=4 and P represents the parameters for each vertex of the quadrilateral.
It is appreciated that computer graphic systems have various processors that perform different tasks. In standard computer graphic systems, a main microprocessor performs some of the specialized steps required to generate a graphic primitive onto the display screen ("render the primitive") and leaves other tasks to a "scan conversion" hardware unit that is tailored to generate a specific type of graphic primitive onto the display screen. The scan conversion typically refers to the fixed point iteration section of the rendering process. Computer graphic systems utilize a display screen that is composed of addressable picture elements called pixels that are arranged in a matrix on the display screen. Graphic primitives are displayed by illuminating the pixels on the display screen that correspond to the desired positional location of graphic primitive. It is appreciated that since pixel sizes are not infinitely small, the actual display of a graphic primitive will be an approximation of that primitive using a pixel pattern on the display screen. Of course, the smaller the pixel size the better the resolution of the displayed primitive. Therefore, since primitives are displayed on a computer screen utilizing pixels, it is the task of the specialized scan conversion hardware to convert a graphic primitive stored in a data structure, TRIANGLE[V][P], into a pattern of pixels for display, this pixel pattern is often called a bitmap and the action of generating the pixel pattern is called a scan conversion since the pattern is generated a pixel line at a time in a "scanned" fashion.
FIG. 1 illustrates the triangle primitive 20. Coordinate indicator 15 is illustrated to show the x and y scheme used in this discussion; the x and y coordinate values represent the two dimensional coordinate scheme used on the screen display. In the prior art, a main processor of a computer graphic system, or multiple processors, will input the data structure, TRIANGLE[V][P], and via a specialized routine calculate the slopes (dx/dy).sub.1, (dx/dy).sub.2, and (dx/dy).sub.3, which are illustrated in FIG. 1 as slopes 10, 12, and 11 respectively of the edges of the triangle primitive. Slope 10 is the slope of the line from vertex 5 to vertex 7 while slope 11 is the slope of the line from vertex 5 to vertex 6. Slope 12 is the slope of the line from vertex 6 to vertex 7. By calculating these slopes and supplying them to the scan conversion hardware, the scan conversion hardware can determine which pixels lie within the triangle primitive for display. In order to compute these three slopes, the main processor of the computer graphics system must be presented with the triangle data structure with the vertex data arranged in a particular order.
In the case of a triangle primitive, the main processor, due to interests of speed, has specialized routines ("processors") that are designed to first accept the vertex having the largest y coordinate value as the vertex in position 5 (assume the first vertex data read), secondly accept the vertex with the middle y coordinate value as the vertex in position 6 (assume the second vertex data read), and then accept the vertex having the smallest y coordinate value as the vertex in position 7 (assume the last vertex). The exact order of receipt of this data for any given ymax, ymid, or ymin value is not important, what is vital is that the routine be able to predict the vertex having the ymin or ymid or ymax value depending on the order in which the vertices were passed to the specialized routine. In this example, the routine must always have ymax sent first, then ymid, then lastly ymin. This is the case because the slope calculation as shown in FIG. 1, assume for slope 1, involves (ymax-ymin), and for slope 2 requires (ymid-ymin), and for slope 3 requires (ymax-ymin). (It is appreciated that the terminology xmax within FIG. 1 does not refer to the maximum x value of the three vertices 5, 6, 7, but rather refers to the x coordinate location of the ymax vertex; therefore xmax is the x coordinate for vertex 5, xmid is the x coordinate of vertex 6, and xmin is the x coordinate for vertex 7.) Due to processing time constraints, the specialized routine is not able to determine (or does not have the time to determine) which vertex contains which y value. The y value order must be communicated to the specialized routine by virtue of the order or fashion in which the vertices 5, 6, 7 are supplied to the routine. Therefore, it is advantageous to develop a system that will quickly and efficiently supply a primitive's vertex data to a specialized routine in the order (of ymid, ymin, ymax) that the specialized routine expects.
The specialized routines of the computer system also calculate several partial derivatives, 21-25 of FIG. 1, (for both dx and dy) of the parameters contained within the data structure for the triangle primitive 20. Partial derivatives 21 (dr/dx, and dr/dy) indicate the change in red parameter for each pixel location change in the x direction and for each change in the y direction, respectively, for the pixels located within the triangle primitive 20. Likewise partial derivatives 22 and 23 indicate the change in green color and change in blue color for every pixel location change in x and y, respectively, for the pixels located within the triangle primitive. The routine computes these values by first calculating, for each, specialized end point values of pixels located on the edges and vertices of the primitive. For example, to compute the partial derivatives 21 for red, the main routine first obtains the red value for the vertex 6 (associated with ymid) which should be directly available from the data structure TRIANGLE[V][P]; this value is called red1. Next, the computer routine calculates the coordinates of point 8 along the line from ymax to ymin that intersects the line having the equation of y=ymid. The computer routine then computes the values of red at this point 8 based on the values of red stored for vectors 5 and 7 which are available within the data structure for primitive 20, this value is called red2. This calculation of red2 is performed by first determining an equation for the parameter of red along the line from vertex 5 to vertex 7 and then computing the red value at point 8, along that line. The partial derivative (dr/dx) will then be the difference between the red2 value and the red1 value divided by the difference between the x coordinates at point 8 and at vertex 6 (ymid). The computer routine performs this calculation.
The other partial derivative, dr/dy of 21, is computed in a similar method. First, either vertex 5 or vertex 7 is selected. It is preferred that the vertex having the middle x coordinate is used. For this example, vertex 7 is selected, its red value is recorded by the data structure and is red3. A line having an equation of the x coordinate value of vertex 7 is projected onto the line from ymax vertex 5 to ymid vertex 6 to solve for the location of point 9. Similarly, the red value at point 9 is computed as a function of the red value at vertex 5, the red value at vertex 6 and the location of point 9 along the line between vertex 5 and vertex 6; this red value is called red4. Then, the partial derivative dr/dy is computed as the difference between red4 and red3 divided by the difference between the y coordinate values at point ymin vertex 7 and at point 9. The above explanation can be extended to apply to the other partial derivatives 22-25 and any others that may be employed to constitute the graphic primitive 20.
The computer routine or ("processor") then completes several sub-pixel correction computations for the triangle primitive 20. Pixel points xminL 26 and xminR 27 are also computed by the computer routine as the lowest rightmost and leftmost pixels that form the primitive 20. These points may or may not lie on the edge of the primitive because the pixel pattern will only be an approximation of the primitive and therefore the edge of the polygon may fall in a space between adjacent pixels. These points, 26 and 27, represent the sub-pixel corrections to the nearest scan line that will be used to generate the pixels for display; this can be done by approximating the (x, y) values of points 26 and 27 to the nearest integer values of the y coordinate along the [ymid, ymin] and [ymax, ymin] vectors. Along with these two pixel points, 26 and 27, the computer processor computes the initial values of each parameter (i.e., color, etc.) in order to set the initial values used for the scan conversion hardware for these points. In so doing, when the specialized computer routine sends the scan conversion hardware the initial values (for points 26 and 27), the scan conversion hardware can utilize the partial derivatives to determine the attributes of each pixel within the primitive 20 according to its relative displacement in x and y from the initial points 26 and 27. The scan conversion hardware determines the locations of the points within the polygon 20 by using the three slope equations supplied.
Therefore, for each triangle primitive the computer processor's specialized routine performs the functions of: (1) generating the three slope equations 10, 12, 11; (2) generating the partial derivatives for each of the parameters 21-25; (3) performing subpixel corrections by generating the initial locations and parameters for points 26 and 27 and then (4) transferring all of this information to a specialized hardware scan conversion hardware unit which will generate the actual pixel pattern or bitmap for the geometric primitive 20. The specialized scan conversion hardware will then begin to generate all of the pixels for the display of the primitive once it has all of the initialization data, the slopes and the partial derivatives. The way in which the scan conversion hardware generates the pattern is well known in graphics technology and it may be done in a scanning fashion either horizontally, or vertically with scan lines. Basically, the hardware starts at points 26, 27 and will generate horizontal scan lines across the entire primitive until all of the pixels are generated. It will determine the pixels within each horizontal scan line (having a particular y coordinate) by using the supplied slopes. It will determine the other parameters of each pixel by utilizing the initial values of these parameters from the pixels 26 and 27 and by calculating addition or subtraction values based on the partial derivatives and the x and y displacements of each pixel from the initial points 26 and 27. The hardware processing unit will continue until each pixel within the primitive is generated and output to the display screen. Then, the specialized computer routine and the scan conversion hardware will be ready for another graphic primitive to render.
The important aspect of these specialized computer routines for generating slopes, partial derivatives and sub-pixel corrections is that they require the vertex data of a triangle primitive's data structure to arrive within a specific order (i.e., ymax, ymid, ymin). Therefore, it is advantageous for a computer graphics system to provide such order without the need for multiple branch testing in software. To this extent, the detail of the performance of such specialized computer processors and hardware scan converters is not required for a complete understanding of the present invention. However, for more background information regarding the details of such a hardware generation circuit refer to the copending application Ser. No. 7-657,087 entitled Method for Scan Converting Shaded Triangular Polygons and for Determining the Coverage of Pixels in Polygons, which was filed on Feb. 19, 1991 and assigned to the assignee of the present patent application.
As discussed previously, the specialized routine for performing the slope, partial derivative, and sub-pixel correction calculations expects to receive the vertices of an input triangle primitive in a particular order, determined by y screen coordinate values of the vertices, or alternatively, based on the x screen coordinate values of the vertices. However, the vertices within the data structures of the primitives are not stored in such an order. Rather, the data structures containing the vertices are stored according to an arbitrary fashion by selecting one vertex as vertex0 and then rotating around the triangle to select the other vertices, vertex1 and vertex2, or for a quad primitive to select an arbitrary vertex for vertex0 and then rotating around the quadrilateral to select vertices 1, 2 and 3. The reason for this is that the computer graphics program can and does generate vertices in this arbitrary order.
Therefore, since the vertex data for primitives are not stored in any order with respect to the y screen value, and further since the specialized processors of the graphic system requires that it be supplied vertex data in a particular order corresponding to the y screen values, the computer processor must perform several comparison operations in order to determine which vertex within a triangle primitive's data structure is the maximum y vertex (ymax), the middle y vertex (ymid) and the minimum y vertex (ymin). Given a basic triangle geometric primitive having three vertices, there are six different possible orderings of vertices. For instance, vertex0 could have a y value larger than the y value of vertex1 which is larger than the y value of vertex 2 for an arrangement called "0&gt;1&gt;2." There could also be: 1&gt;0&gt;2, or 0&gt;2&gt;1, or 2&gt;0&gt;1 or 1&gt;2&gt;0 or lastly 2&gt;1&gt;0. The computer processor must compare each of the vertices to determine in which order they lie. When two of the vertices are equal, the ordering may adopt one of the above combinations. If the condition is (ymax&gt;ymid=ymin) then the (ymax&gt;ymid&gt;ymin) case may be used or the (ymax&gt;ymin&gt;ymid) case can be used. Likewise, if the (ymax=ymid&gt;ymin) is case is present then the (ymax&gt;ymid&gt;ymin) case may be used or the (ymid&gt;ymax&gt;ymin) case can be used. As shown, the equal vertices are completely interchangeable. If the all vertices are equal (i.e., a line) then they can adopt any of the six above cases.
It is appreciated that due to the vast number of calculations performed by a graphics processor, the need for efficiency is great. In order words, there is not enough processing time or power in order for the computer processor to rearrange the vertices of a particular triangle primitive to match the order that is expected for any given or particular specialized processor (i.e. for slope, partial derivatives, or sub-pixel corrections). Instead, in high performance graphics processors, a separate specialized routine is supplied for each of the six possible combinations of vertex orderings based on y coordinate values. There is a separate specialized routine tailored to process the 0&gt;1&gt;2 case, one for the 0&gt;2&gt;1 case, one for the 1&gt;2&gt;0 case, and so forth for each of the above six cases. The computer processor only has to determine which case is present within an input triangle primitive (i.e., which of the six orderings is present) by using a branch condition for each, and then channel processing to that particular specialized routine. In so doing the data does not have to be rearranged to match a particular routine, rather, there is a separate routine for each of the six cases.
Prior Art Process Flow for Triangle and Quadrilateral Rendering
The steps required for a prior art computer graphic processor to render a triangle primitive are illustrated in flow diagrams of FIG. 2(A) and FIG. 2(B). The entire flow illustrated in FIG. 2(A) and FIG. 2(B) is referred to as the 201 flow. The processing starts at block 200 and continues to block 205 where the three vertices of the triangle data structure are received from memory, in fact, the entire primitive data structure including: 1) positional location data (x, y, z) in world coordinate space; 2) color attributes; 3) surface normal data; 4) and other data, is received for each vertex of the primitive into the processor memory. At block 210 the vertices of the primitive are transformed from the world coordinate (x, y, z) space (described from a world reference point) which presents all the environment of the display data stored within the computer system into an eye coordinate space. Eye coordinate space represents the coordinates of the vertices in three dimensional space which is referenced from the point at which the viewer's eye is located and the particular angle of sight employed by the viewer. At block 210 each of the vertices and surface normals associated with the primitive are transformed from the initial world coordinate into the eye coordinate depending on the location and line of sight of the viewing eye in three dimensional space.
Next, the processor reaches the first branch test at block 220 and tests if any vertices are within a clip volume. Very infrequently this process follows the "yes" 220a path during typical process flow and is shown merely to be complete. Block 225 can be viewed as an exception handler. Polygon clipping will be performed within block 225 which is a different process of which the present invention is not concerned. As most likely will be the case, flow of the computer processor will continue to block 230 via condition flow 220b. At block 230, the three dimensional triangle primitive will be "projected" onto a two dimensional viewing screen. That is, at block 230 the primitive will be transformed from the three dimensional eye coordinates (x, y, z) and projected onto the plane of the viewing screen in two dimensions (x, y), see indicator 15 of FIG. 1. These viewing screen coordinates are called screen x and screen y values.
At block 235 the computer processor then performs the comparison functions as described above to determine the particular ordering of the triangle vertices depending on their screen y values. First, vertex 0 is compared to vertex 1 (the 01 compare), then vertex 0 is compared to vertex 2 (the 02 compare), then vertex 1 is compared to vertex 2 (the 12 compare). At the completion of the processing of block 235 the computer processor will know which of the six vertex orderings the data structure of the present triangle primitive contains. Processing of FIG. 2(A) then proceeds to the processing of FIG. 2(B) via block 240. FIG. 2(B) illustrates six separate branching paths formed by five conditional branching paths and one default condition (270). Each of the branching paths leads to a specially tailored process for generating the triangle primitive having a particular vertex ordering according to the y screen value. At block 245, the 2&gt;1&gt;0 condition is checked, and if encountered processing proceeds to block 247 where the vertices are accessed from the computer memory and the specialized process computes the three slopes, the partial derivatives, the sub-pixel corrections, and the initialization points 26 and 27. These processes are accomplished based on the ordering of vertices 2&gt;1&gt;0 with respect to the y screen values.
After the processing of block 247, the computer processor then performs block 248 which loads the determined slopes, partial derivatives, initialization values, and sub-pixel corrections into the specialized scan conversion hardware and enables the hardware to generate and display the pixel pattern representing the triangle primitive. Processing then proceeds to block 285 to either start again with a new triangle primitive or return from flow 201 if called from an outside routine. If the current triangle primitive is not 2&gt;1&gt;0 then the processing continues to block 250 to check for the 1&gt;2&gt;0 condition. If this condition is met then processing continues to block 252 to perform the slope, partial derivative, sub-pixel correction and initializing computations based on this order. Next, at block 253 the hardware is given the data from block 252 to generate and display the triangle primitive and return to block 208 when complete. If the condition at block 250 fails, then processing continues to block 255 where condition 2&gt;0&gt;1 is tested. If this condition is encountered, then block 257 will be executed based on 2&gt;0&gt;1 order and block 258 will generate and display the triangle primitive and return to block 285. If the condition at block 255 fails, then processing continues to block 260 where condition 0&gt;2&gt;1 is tested. If this condition is encountered, then block 262 will be executed based on 0&gt;2&gt;1 order and block 263 will generate and display the triangle primitive and return to block 285. If the condition at block 260 fails, then processing continues to block 265 where condition 1&gt;0&gt;2 is tested. If this condition is encountered, then block 267 will be executed based on 1&gt;0&gt;2 order and block 268 will generate and display the triangle primitive and return to block 285. If block 265 fails then either of two cases is true. First, graphic primitive may contain the order 0&gt;1&gt;2 or second, it may contain equals between all three vertices. In either cases, block 270 is executed to supply the required data to the scan converter hardware at block 280 which generates and displays the triangle on the screen. At block 285 the processing returns to block 200.
It is appreciated that each of the above blocks 247, 252, 257, 262, 267, and 270 of the triangle processing flow 201 perform the exact same computations (slope, sub-pixel correction, partial derivative, and initialization values), but for data structures having different vertex orderings.
The steps required for a computer graphic processor to render a quadrilateral primitive are illustrated in flow diagrams of FIG. 3(A) and FIG. 3(B). As will be shown, quadrilateral primitive is typically split across opposing vertices in order to generate two triangle primitives, each using three vertices of the quadrilateral polygon. Then each of the two triangles is processed similar to the triangle rendering processing blocks 235 to 280 as described above. The flow for the quadrilateral process of the computer processor begins at 300 and flows to 305 where the data structure for the quadrilateral is received into the computer processor memory. This data structure contains, for each of the four vertices, location, color, surface normal, and other information required to render the quadrilateral primitive. At block 310 the quadrilateral vertices and surface normals are transformed from the three dimensional world coordinate system into the eye coordinate system in three dimensions also. Then at block 315 the exception handling quadrilateral clipping branch is tested to see if any polygon clipping is required. If so, then processing continues out of the current flow to block 320 and the present invention is not concerned with this flow. Typically, the flow will go to block 320 because clipping is rare. At block 325 a perspective divide, or projection, is done from the three dimensional eye coordinate scheme into the two dimensional (x, y) screen coordinates of the display plane. This is done for each of the data of the vertices of the quadrilateral including the surface normal vectors.
At block 330, the computer processor computes the dot products of surface normals for vectors 0 and 2 and then the dot product for surface normals for vectors 1 and 3. At block 340 of FIG. 3(B) these values are compared. If the dot product of the surface normals for vectors 0 and 2 is larger then the dot product of the surface normals for vectors 1 and 3 then processing goes to block 365, else it goes to block 345. At block 365 the quadrilateral polygon is split into two triangles across opposing vertices 1 and 3, the first triangle being vectors (0, 1, 3) and the second triangle being vectors (1, 2, 3) of the quadrilateral. At block 370 the triangle rendering flow processing blocks 235-280 are performed for the first triangle (0, 1, 3) and then processing will return to block 370. Next at block 380, the triangle rendering flow blocks 235-280 are performed on the second triangle (1, 2, 3) and processing returns to block 380. After these flows, block 385 readies the processor for the next quadrilateral data structure.
Notice that for each triangle processed there were six separate branching conditions tested for each of the possible vertex orderings as described within flows 235-280. Therefore, for each quadrilateral primitive there are twelve branching conditions tested by the program flow and six separate specialized processor routines that will be performed.
At block 345 the quadrilateral is split across opposing vertices 0 and 2 instead of 1 and 3. Therefore, triangle (0, 1, 2) is created and triangle (0, 2, 3) is created. At block 350, the first triangle is sent through process flow blocks 235-280 and at block 360 the second triangle is sent through process flow blocks 235-280. At block 385 the computer processor readies for the next quadrilateral data structure. Again, for each quadrilateral there are twelve branching conditions tested by the program flow and six separate specialized processor routines that will be performed.